#ifndef __WORDCOUNTER_H__
#define __WORDCOUNTER_H__

#include <stdio.h>

#define MAX_WORD_LEN 63
#define _HASH_TABLE_LENGTH 128

typedef struct word_t word_t;

/*
 * hash_link_t helps to implement two data structure - a hash table and a
 * linked list. When there is a collision in hashing of two words then
 * hash_collision_next points to next word that has same hash key.
 * linked_list_next helps to efficiently parse all the entries in hash
 * table if hash table is sparsely populated.
 */
typedef struct hash_link_t
{
  /* points to next link in hash collision list */
  word_t *hash_collision_next;
  /* points to next word - a time optimization to prevent scanning
   * entire hash table*/
  word_t *linked_list_next;
} hash_link_t;


/*
 * bin_tree_t is the data structure to sort the words based on the frequency
 * of their occurrences.
 */
typedef struct bin_tree_t
{
  word_t *left_node;
  word_t *right_node;
} bin_tree_t;

/*
 * The Parsing and comparing of all the words is done before starting to sort
 * the words based on the occurrence. At a given time only one of
 * hash-linked-list or binary tree is active. Union is used to take advantage
 * of this process as it will save on space utilized. 
 */

typedef union hash_or_tree_t
{
  hash_link_t hash_link;
  bin_tree_t tree;
} hash_or_tree_t;


/*
 * The core data structure of word_counter routine.
 * The current implementation array of characters rather than malloc'd memory.
 * The length of word is limited by macro MAX_WORD_LEN.
 * In future this can be changed to use malloc'd char string, if needed. 
 */
struct word_t
{
  char s_word[MAX_WORD_LEN + 1];	/* The word */
  int freq;			/* word frequency counter */
  hash_or_tree_t hash_tree;
};


/*
 * hash_dictionary data structure stores the hash table and head of the linked
 * list of words. This structure remains active only when we are parsing
 * the words or searching already parsed words. linked_list_head points makes
 * parsing the hash table to sort the words on frequency of appearance.
 */
typedef struct hash_dictionary
{
  word_t *hash_table[_HASH_TABLE_LENGTH];
  word_t *linked_list_head;
} hash_dictionary_t;


/* get_hash_key returns the hash key for a given word */
int get_hash_key (char *value);

/* init_hash_dictionary initializes  hash_dictionary_t */
void init_hash_dictionary (hash_dictionary_t * dictionary);

/* insert_in_hash_dictionary inserts a word in dictionary or frequency++ */
int insert_in_hash_dictionary (hash_dictionary_t * dictionary, char *value);

/* build_tree_from_dictionary converts hash table to bin tree sorted on freq */
word_t *build_tree_from_dictionary (hash_dictionary_t * dictionary);

/* insert_tree_node - a worker routine to add a node to tree */
void insert_tree_node (word_t * top, word_t * node);

/* print_tree - a tree traversal and printer routine */
void print_tree (word_t * root, FILE * output);

/* 
 * cleanup routine, called while returning from error condition.
 * Should cleanup the malloc'd memory
 */
int cleanup ();


#endif
